package linkedList;

import linkedList.entity.ListNode;

/**
 * @Desc: 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 * 示例 1：
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 *
 * 示例 2：
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 * @Author: lxf
 * @Date: 20240307
 */
public class ReverseBetween {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(0);
        ListNode tail1 = head1;
        for (int i = 1; i < 5; i++) {
            ListNode p = new ListNode(i);
            tail1.next = p;
            tail1 = p;
        }
        reverse(head1);
    }
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode preLeftTail = null;
        ListNode afterRight = null;
        ListNode reverseListTail = null;
        ListNode reverseListHead = reverseListTail;
        ListNode p = head;
        int index = 1;
        while (p != null){
            ListNode next = p.next;
            if (left-1 == index){
                preLeftTail = p;
            }
            if (right+1 == index){
                afterRight = p;
                break;
            }
            if (index>=left && index<=right){
                if (reverseListTail == null) {
                    reverseListTail = reverseListHead = p;
                }else {
                    p.next = reverseListHead;
                    reverseListHead = p;
                }
            }
            p = next;
            index++;
        }
        if (preLeftTail != null) {
            preLeftTail.next = reverseListHead;
        }
        reverseListTail.next = afterRight;
        return preLeftTail == null?reverseListHead:head;
    }


    /*
    *穿针引线法反转链表
    * */
    public static ListNode reverse(ListNode head){
        if (head.next == null){
            return head;
        }
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode next;
        ListNode cul = head;
        while (cul.next != null){
            next = cul.next;
            cul.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return pre.next;
    }
    /*
     *假头法反转链表
     * */
    public static ListNode reverse2(ListNode head){
        if (head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode cul = head;
        while (cul != null){
            ListNode next = cul.next;
            cul.next = pre;
            pre = cul;
            cul = next;
        }
        return pre;
    }
}
